Fishes [A]

Memory limit: 256 MB

In an archipelago far away, there lives a rare predator fish species. They have a very regular rhythm of life. Each fish wakes up every morning at the same time of day and goes hunting. In the evening, it returns to the place, from which it set off. It goes to sleep there (every day at the same time), but it can wake up in a different place, as it can be moved a little by ocean currents.

During the whole day, a fish sticks to the following rule: in every moment it has to see the place, in which it was at the same time of the previous day, that is exactly 24 hours earlier. Of course, a fish cannot see a point which is on the opposite side of some island.

Ichthyologists have been observing fishes in the archipelago for quite a long time and every couple of days they took record of one route of some fish. Unfortunately, after collecting large amounts of data, there has been an accident. Some of the data is missing and the rest is completely messed up. The scientists do not even know which fish traveled each route they have recorded. They asked you for help. They are going to give you the messed up descriptions of fishes' routes and ask you to tell them what could be the minimal number of different fishes, that they have observed during their research.

Input

Your program should read the data from the standard input. The input consists of two parts: a description of the archipelago and a description of fishes' routes. The first line of the archipelago description contains two integers and (, ), separated by a single space. In each of the following lines, there is a character long string that describes a part of archipelago. A character '.' represents ocean, whereas '#' - land. In all cells on the boundary of the map, there is water ('.' character).

One point in the archipelago is visible from another, if a segment connecting them does not have common points with interior or boundary of any piece of land. The direction in which a fish is swimming does not matter here.

In the next line, there is an integer (), the number of recorded fishes' routes. The following lines contain descriptions of those routes. In the first line of a route description, there are three integers , , and (, , ), separated by single spaces. and are the coordinates of the place where a fish woke up (column and row) and is the length of the route. The second line is a string of characters N, W, S or E, representing the direction of fish. They stand for up, left, down and right respectively. It is guaranteed that the routes go only through cells with water, fishes do not leave the fragment of archipelago described in the input and the beginning and end of each route are in the same cell.

A fish can only move horizontally or vertically; it swims along a broken line, which connects the centers of the cells on its way. However, we do not know what its speed is. The fish can speed up or slow down in order to always see the point in which it was exactly 24 hours earlier.

Ocean currents can move the sleeping fish at most one cell up, down left or right from the place in which the fish went to sleep. You can assume, that for every two water cells in the archipelago, there exists some (hypothetical) fish route that goes through both of them.

Output

In the first line of the standard output your program should write out an integer - the smallest possible number of different fishes, that is consistent with the data gathered by the scientists. Each of the following lines should contain a list of routes of a single fish. The fish did not necessarily need to swim along those routes in consecutive days, but in any two days of its life.

A fish can travel two routes in two consecutive days, if both routes start in the same or neighboring cells (cells sharing an edge) and if the fish could swim along the second route, being able to see the point in which it was exactly 24 hours earlier all the time.

The routes are numbered from to , according to their order in the input. Numbers of routes in each line of the output should be written in increasing order and the lines should be ordered in such a way, that first numbers in all lines form an increasing sequence.

Example

For the input data:

10 8
..........
.......#..
........#.
..........
...#......
......###.
......###.
..........
4
2 7 12
NNNEEESSSWWW
2 8 24
WNNNNNNNEEEEESSSSSSSWWWW
1 8 46
NNNNNNNEEEEESSSSSSSEEEENNNNNNNSSSSSSSWWWWWWWWW
1 8 32
NNNNNNNEEEEEEEEESSSSSSSWWWWWWWWW

the correct result is:

2
1 2 3
4

Explanation of the example. The first two routes could have been traveled by the same fish (even in two consecutive days). After few days, the fish could have followed the third route. However, the last route must have been traveled by another fish. Contrary to the first three routes, it goes around the big island.

Task author: Eryk Kopczynski.